from typing import List


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        max_value = 0
        n = len(satisfaction)
        s = 0
        for i in range(n):
            if satisfaction[i] > 0:
                s = i
                break
        # 从后向前
        def helper(start, level, ans):
            print(start, level, ans)
            nonlocal max_value
            max_value = max(ans, max_value)
            # print(ans)
            for i in range(start, n):
                helper(i + 1, level + 1, ans + level * satisfaction[i])

        helper(0, 1, 0)
        return max_value


if __name__ == "__main__":
    print(
        Solution().maxSatisfaction(
            [-1,-8,0,5,-9]
        )
    )
